#include<bits/stdc++.h>
using namespace std;
int a[20],b[20],c[20],d[20],n,s,total = 1;
void printf()
{
	int i;
	s++;
	cout << total << ":";
	for (i = 1;i <= n;i++)
	{
		cout << a[i];
	}
	cout << endl;
	total++;
}
int search(int i)
{	
	int j;
	for (j = 1;j <= n;j++)
	{
		if (b[j] == 0 && c[i + j] == 0 && d[i - j + n] == 0)
		{
			a[i] = j;
			b[j] = 1;
			c[i + j] = 1;
			d[i - j + n] = 1;
			if(i == n)
			{
				printf();
			}
			else
			{
				search(i + 1);
			}
			b[j] = 0;
			c[i + j] = 0;
			d[i - j + n] = 0;
		}
	}	
} 
int main()
{	
	cin >> n;
	search(1);
	return 0;
}
